public class code8 {
    //四数之和
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int n = nums.length;
        List<List<Integer>> ret = new ArrayList<>();
        //1.排序
        Arrays.sort(nums);
        //2.固定两个数
        for(int i=0;i<n-3;) {
            for(int j=i+1;j<n-2;) {
                int left=j+1,right=n-1;
                while(left<right) {
                    long sum = (long)nums[i]+nums[j]+nums[left]+nums[right];
                    if(sum<target) left++;
                    else if(sum>target) right--;
                    else {
                        ret.add(new ArrayList<Integer>(Arrays.asList(nums[i],nums[j],nums[left],nums[right])));
                        left++;right--;
                        while(left<right && nums[left]==nums[left-1]) left++;
                        while(left<right && nums[right]==nums[right+1]) right--;
                    }
                }
                j++;
                while(j<n && nums[j]==nums[j-1]) j++;
            }
            i++;
            while(i<n && nums[i]==nums[i-1]) i++;
        }
        return ret;
    }
}
